package com.leetcode.demo10;

import java.util.HashMap;
import java.util.List;

public class Solution {


/*    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) {
            return text.isEmpty();
        }
        //文本非空 && [(样式首字母==文本首字母)||样式的首字母为.]
        boolean first_match =
        (
                !text.isEmpty() &&
                (pattern.charAt(0) == text.charAt(0)||pattern.charAt(0)=='.')
        );
        //只有样式的长度大于2的时候才考虑*
        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            //pattern直接跳过两个字符，表示*前面的字符出现0次
            //pattern不变 ，如 text=aa ,pattern=a* 第一个a匹配，然后text的第二个a接着还是和pattern的第一个a匹配，
            // * 表示用前一个字符替代
            //两个递归结束条件
            return ( isMatch(text,pattern.substring(2)) || (first_match && isMatch(text.substring(1),pattern)));
        } else {
            //第一个元素匹配 && 后面的每一个单独的元素也是要匹配的
            return first_match && isMatch(text.substring(1),pattern.substring(1));
        }
    }  //时间复杂度和空间复杂度都很高*/


    public boolean isMatch(String text , String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        //字符串和模式都为空，也属于匹配的情况
        dp[text.length()][pattern.length()] = true ;
        for (int i = text.length(); i >= 0 ; i--) {
            for (int j = pattern.length() ; j >=0  ; j-- ) {
                //跳过已经初始化的最后一个元素
                if (i==text.length() && j==pattern.length()) continue;
                boolean first_match = (i < text.length() && j<pattern.length()
                                        && (pattern.charAt(j) == text.charAt(i)||
                                            pattern.charAt(j)=='.'));
                if (j+1 <pattern.length() && pattern.charAt(j+1)=='*') {
                    dp[i][j]=dp[i][j+2] || first_match && dp[i+1][j];

                }else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }

            }
        }

        return dp[0][0];
    }





}
